/*
	Copyright (c) 2008, Grant Jones <grant@podtronics.com>.
	All rights reserved.

	Redistribution and use in source and binary forms, with or
	without modification, are permitted provided that the following
	conditions are met:

		Redistributions of source code must retain the above copyright
		notice, this list of conditions and the following disclaimer.
		
		Redistributions in binary form must reproduce the above copyright
		notice, this list of conditions and the following disclaimer in
		the documentation and/or other materials provided with the
		distribution.
		
		Neither the name of the gxjones.com nor the names of its
		contributors may be used to endorse or promote products derived
		from this software without specific prior written permission.
	
	THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
	"AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
	LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
	FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
	COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
	INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
	(INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
	SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
	HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
	STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
	ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
	OF THE POSSIBILITY OF SUCH DAMAGE.
	
	http://www.opensource.org/licenses/bsd-license.php
*/

/*
 *  tagm.c
 *  edb
 *
 *  Created by Grant Jones on 4/30/07.
 *
 */

#include "tagm.h"
#include "tagmt.h"


TagManagerStruct *tagm_open( const char *tags_filename )
{
	TagManagerStruct *tags;
	struct stat sb;
//	printf("TagHdrStruct size is %d bytes\n", sizeof(TagHdrStruct) );
	
	tags = (TagManagerStruct *)malloc( sizeof(TagManagerStruct) );
	if(!tags)
		return NULL;
	memset( tags, 0, sizeof(TagManagerStruct) );
	
	tagmt_init( tags );
	
#ifdef TAGM_DEBUG_NAME
	strcpy( tags->name, tags_filename );
#endif


	if( tags_filename )
	{	
		tags->fd = open( tags_filename, O_CREAT | O_RDWR /*| O_EXLOCK*/, 0660 );
		if(tags->fd < 0 )
		{
			printf("failed to open tags file: %s\n", tags_filename );
			free( tags );
			return NULL;
		}
		
		if( fstat( tags->fd, &sb ) )
		{
			printf("unable to stat index file: %s\n", strerror(errno) );
			tagm_close(tags);
			return NULL;
		}
		
		tags->tag_file_sz = sb.st_size;
	}
	else
	{
		/* memory tag file */
		tags->tag_file_sz = 0;
		tags->fd = -1;
		tagmt_beginTransaction(tags);
	}
	
	if( tags->tag_file_sz == 0 )
	{
		if( tagm_zerofile( tags ) )
		{
			tagm_close(tags);
			return NULL;
		}
	}
	
	
	
	return tags;
}


void tagm_close( TagManagerStruct *tags )
{
	if(!tags) return;
	if( tags->fd >= 0 )
		close( tags->fd );
	else
	{
		tagmt_endTransaction(tags, 1);		
	}
	free(tags);
}

/* ************************************************************************
************************************************************************ */
/*!
	@function tagm_zerofile
	@abstract Removes everything from the target tag manager context
	@discussion Zeroes the root item (and clears the free tag)
	@result returns the current transaction ID; -1 on error
*/
int tagm_zerofile( TagManagerStruct *tags )
{
	TagHdrStruct ths;
	memset( &ths, 0, sizeof(TagHdrStruct) );
	// need to create the root item
	if( tagmt_pwrite( tags, &ths, sizeof(TagHdrStruct), 0ULL ) != sizeof(TagHdrStruct) )
	{
		printf("unable to write root item to tag file (%s)\n", strerror(errno) );
		return -1;
	}
	// need to create deleted list item
	if( tagmt_pwrite( tags, &ths, sizeof(TagHdrStruct), sizeof(TagHdrStruct) ) != sizeof(TagHdrStruct) )
	{
		printf("unable to write root item to tag file (%s)\n", strerror(errno) );
		return -1;
	}		

	tags->tag_file_sz = sizeof(TagHdrStruct);		// should be *2?

	return 0;
}

/* ************************************************************************
************************************************************************ */

int tagm_beginEnumTags( TagManagerStruct *tags, TagManagerEnumStruct *tmes, off_t root_loc )
{
	TagHdrStruct ths;
	tmes->cur_loc = 0ULL;
	tmes->data_alloc_sz = 0ULL;
	tmes->curTag.data = NULL;
	tmes->key_alloc_sz = 0ULL;
	tmes->curTag.key = NULL;
	
	if( tagmt_pread(tags,&ths,sizeof(TagHdrStruct), root_loc ) != sizeof(TagHdrStruct) )
	{
		printf("couldn't beginTagList (%s)\n", strerror(errno) );
		return -1;
	}
	
//	printf("root item -> first location: %d\n", ts.first );
	if( ths.first == 0 )
		return 0;
	
	tmes->cur_loc = ths.first;
	return 0;
}

int tagm_endEnumTags( TagManagerStruct *tags, TagManagerEnumStruct *tmes )
{
	if( tmes->curTag.key )
		free( tmes->curTag.key );
	if( tmes->curTag.data )
		free( tmes->curTag.data );
	return 0;
}

// call this to only read the next tag's header:
int tagm_nextTagHeader( TagManagerStruct *tags, TagManagerEnumStruct *tmes, off_t *tag_loc, TagHdrStruct *tag_hdr )
{
	if( tmes->cur_loc == 0 )
		return -1;
	
	*tag_loc = tmes->cur_loc;
	
	if( tagmt_pread(tags,&tmes->curTag.hdr,sizeof(TagHdrStruct), tmes->cur_loc ) != sizeof(TagHdrStruct) )
	{
		printf("couldn't tagm_nextTagHeader (%s)\n", strerror(errno) );
		return -1;
	}
	
	memcpy( tag_hdr, &tmes->curTag.hdr, sizeof(TagHdrStruct) );
			
	tmes->cur_loc = tmes->curTag.hdr.next;
	
	return 0;	
}

// call this to read the next tag's header and key/data:
TagStruct *tagm_nextTag( TagManagerStruct *tags, TagManagerEnumStruct *tmes, off_t *tag_loc )
{
	// locate another undeleted tag:
	for(;;)
	{
		if( tmes->cur_loc == 0 )
			return NULL;

		*tag_loc = tmes->cur_loc;
		if( tagmt_pread(tags,&tmes->curTag.hdr,sizeof(TagHdrStruct), tmes->cur_loc ) != sizeof(TagHdrStruct) )
		{
			printf("couldn't tagm_nextTag (%s)\n", strerror(errno) );
			return NULL;
		}
	
		if( tmes->curTag.hdr.bFlags & TAG_DELETED )
		{
//			TAGM_TRACE(("tagm_nextTag: tag is deleted (%ld)\n",(int)tmes->cur_loc ));
			
			tmes->cur_loc = tmes->curTag.hdr.next;
			
		}
		else
		{
			// the tag is not deleted
			// break and continue on:
			break;
		}
	}
	
	/* read key */
	if( tmes->key_alloc_sz < tmes->curTag.hdr.klen )
	{
		tmes->key_alloc_sz = tmes->curTag.hdr.klen;
		tmes->curTag.key = (unsigned char *)realloc( tmes->curTag.key, tmes->key_alloc_sz );
	}
	
	if( tagmt_pread( tags, tmes->curTag.key, tmes->curTag.hdr.klen, tmes->cur_loc + sizeof(TagHdrStruct) ) != tmes->curTag.hdr.klen )
	{
		printf("failed to read complete tag key: %s\n", strerror(errno) );
		return NULL;
	}

	/* read data */
	//printf("tagm_nextTag to read: %d\n", (int) tmes->curTag.hdr.dlen );
	if( tmes->data_alloc_sz < tmes->curTag.hdr.dlen )
	{
		tmes->data_alloc_sz = tmes->curTag.hdr.dlen;
		tmes->curTag.data = (unsigned char *)realloc( tmes->curTag.data, tmes->data_alloc_sz );
	}
	
	if( tagmt_pread( tags, tmes->curTag.data, tmes->curTag.hdr.dlen, tmes->cur_loc + tmes->curTag.hdr.klen +sizeof(TagHdrStruct) ) != tmes->curTag.hdr.dlen )
	{
		printf("failed to read complete tag data: %s\n", strerror(errno) );
		return NULL;
	}

	
	
	tmes->cur_loc = tmes->curTag.hdr.next;
	
	return &tmes->curTag;
}


/* ************************************************************************
************************************************************************ */
off_t tagm_reserveSpace( TagManagerStruct *tags, size_t size )
{
	/* TODO: be smarter about this! */
	off_t new_loc = tags->tag_file_sz;
	tags->tag_file_sz += size;
/*	printf("new_loc: %ld, size: %ld\n", (int)new_loc, (int)size );*/
	return new_loc;
}

int tagm_insertTag( TagManagerStruct *tags, off_t root_loc, TagStruct *new_tag, off_t *new_tag_loc )
{
/*
	Insertion Steps:
	1. locate a new place for this tag (via tagm_reserveSpace)
	2. write the key/data and a mostly empty header
	3. call changeTagParent on the new tag (which will append the item to the parent at root_loc)
*/

	off_t new_loc = tagm_reserveSpace(tags, sizeof(TagHdrStruct) + new_tag->hdr.dlen + new_tag->hdr.klen );	
	
	*new_tag_loc = new_loc;
	
	new_tag->hdr.parent = 0ULL;
	new_tag->hdr.first = 0ULL;
	new_tag->hdr.last = 0ULL;	
	new_tag->hdr.prev = 0ULL;
	new_tag->hdr.next = 0ULL;
	
	/* all pointers will be zeroed but it does contain the key and data payload sizes */
	if( tagmt_pwrite(tags,&new_tag->hdr,sizeof(TagHdrStruct), new_loc ) != sizeof(TagHdrStruct) )
	{
		printf("couldn't insertTag (%s)\n", strerror(errno) );
		return -1;
	}

	if( new_tag->hdr.klen > 0 )
	{
		if( tagmt_pwrite(tags,new_tag->key,new_tag->hdr.klen, new_loc+sizeof(TagHdrStruct) ) != new_tag->hdr.klen )
		{
			printf("couldn't insertTag (%s)\n", strerror(errno) );
			return -1;
		}
	}
	if( new_tag->hdr.dlen > 0 )
	{
		if( tagmt_pwrite(tags,new_tag->data,new_tag->hdr.dlen, new_loc+new_tag->hdr.klen+sizeof(TagHdrStruct) ) != new_tag->hdr.dlen )
		{
			printf("couldn't insertTag (%s)\n", strerror(errno) );
			return -1;
		}
	}

	if( tagm_changeTagParent( tags, new_loc, root_loc ) )
		return -1;

	return 0;
}

/* ************************************************************************
************************************************************************ */
int tagm_compact( TagManagerStruct *tags, off_t hint_loc )
{
	/* tagm_compact: attempts to regain space that was freed by tag deletion
	The free space will be added to the free-space tag set.
	*/
	
	/* TODO */
	return 0;
}

/* ************************************************************************
************************************************************************ */
/*!
	@function tagm_unlinkTag
	@abstract Marks a tag as deleted.
	@discussion Deleting a tag simply marks the tag header with TAG_DELETED
		Unlike tagm_unlinkTag the tag is not removed from the parents linked
		list.
	@result 0 on success, -1 on error
*/
int tagm_deleteTag( TagManagerStruct *tags, off_t tag_loc )
{
	TagStruct *t = tagm_readTag( tags, tag_loc, 0 );
	if(!t)
		return -1;
	
	/* Mark as deleted */
	t->hdr.bFlags |= TAG_DELETED;
	
	/* write out header */
	if( tagmt_pwrite(tags, &t->hdr, sizeof(TagHdrStruct), tag_loc ) != sizeof(TagHdrStruct) )
	{
		printf("couldn't tagm_deleteTag (read header) (%s)\n", strerror(errno) );
		return -1;
	}
//	TAGM_TRACE(("tagm_deleteTag: %ld (flags: 0x%x)\n", (int)tag_loc, t->hdr.bFlags ));
	
	tagm_freeTag(t);

	/* run trash compactor */
	tagm_compact(tags, tag_loc);
	return 0;
}

/* ************************************************************************
************************************************************************ */

/*!
	@function tagm_unlinkTag
	@abstract unlinks a tag from it's parent's linked-list
	@discussion unlinks a tag from it's parent's linked-list; this may
		involved writing to sibling tags and/or the parent tag. NOTE: The
		tag itself will not be modified!
	@result 0 on success, -1 on error
*/
int tagm_unlinkTag( TagManagerStruct *tags, off_t tag_loc )
{
	assert( tag_loc != 0ULL );
	int result = -1;	/* assume error */
	int tid = -1;		/* assume error */
	off_t parent_tag_loc;
	TagStruct *prev_sib = NULL;
	TagStruct *next_sib = NULL;
	TagStruct *parent = NULL;
	
	TagStruct *t = tagm_readTag( tags, tag_loc, 0 );
	if(!t)
		goto cleanup;
	
	parent_tag_loc = t->hdr.parent;
	parent = tagm_readTag( tags, parent_tag_loc, 0 );
	if(!parent)
		goto cleanup;
	
	
	tid = tagmt_beginTransaction( tags );
	
	if(tid < 0)
		goto cleanup;


	if( parent->hdr.first == parent->hdr.last )
	{
		assert( parent->hdr.first == tag_loc );
		
		/* only one item in the list */
		parent->hdr.first = 0ULL;
		parent->hdr.last = 0ULL;
		
		if( tagmt_pwrite(tags,&parent->hdr,sizeof(TagHdrStruct), parent_tag_loc ) != sizeof(TagHdrStruct) )
		{
			TAGM_ERROR(("couldn't %s (%s)\n", __FUNCTION__, strerror(errno) ));
			goto cleanup;
		}
	}
	else if( parent->hdr.first == tag_loc )
	{
		/* first item in a list of two or more :: there must be a valid t->hdr.next */
		assert( t->hdr.next != 0ULL );
		
		parent->hdr.first = t->hdr.next;
		
		if( tagmt_pwrite(tags,&parent->hdr,sizeof(TagHdrStruct), parent_tag_loc ) != sizeof(TagHdrStruct) )
		{
			TAGM_ERROR(("couldn't %s (%s)\n", __FUNCTION__, strerror(errno) ));
			goto cleanup;
		}
		
	}
	else if( parent->hdr.last == tag_loc )
	{
		/* last item in a list of two or more :: there must be a valid t->hdr.prev */
		assert( t->hdr.prev != 0ULL );
		
		parent->hdr.last = t->hdr.prev;
		
		if( tagmt_pwrite(tags,&parent->hdr,sizeof(TagHdrStruct), parent_tag_loc ) != sizeof(TagHdrStruct) )
		{
			TAGM_ERROR(("couldn't %s (%s)\n", __FUNCTION__, strerror(errno) ));
			goto cleanup;
		}
		
	}

	
	/* we need to modify the siblings now, if any: */
	if( t->hdr.prev != 0ULL )
	{
		prev_sib = tagm_readTag( tags, t->hdr.prev, 0 );		
		if(!prev_sib)
			goto cleanup;
		
		if( prev_sib->hdr.next != tag_loc )		/* This is a consistency error */
			goto cleanup;

		prev_sib->hdr.next = t->hdr.next;		/* t->hdr.next may be == 0, that's ok */

		if( tagmt_pwrite(tags,&prev_sib->hdr,sizeof(TagHdrStruct), t->hdr.prev ) != sizeof(TagHdrStruct) )
		{
			TAGM_ERROR(("couldn't %s (%s)\n", __FUNCTION__, strerror(errno) ));
			goto cleanup;
		}
		
	}
	
	if( t->hdr.next != 0ULL )
	{
		next_sib = tagm_readTag( tags, t->hdr.next, 0 );		
		if(!next_sib)
			goto cleanup;

		if( next_sib->hdr.prev != tag_loc )		/* This is a consistency error */
			goto cleanup;

		next_sib->hdr.prev = t->hdr.prev;		/* t->hdr.prev may be == 0, that's ok */
		
		if( tagmt_pwrite(tags,&next_sib->hdr,sizeof(TagHdrStruct), t->hdr.next ) != sizeof(TagHdrStruct) )
		{
			TAGM_ERROR(("couldn't %s (%s)\n", __FUNCTION__, strerror(errno) ));
			goto cleanup;
		}
	}

	
	result = tagmt_endTransaction( tags, tid );
	
cleanup:	
	/* Abort any mid-transaction failures: */
	if( result < 0 && tid > 0 )
		tagmt_abortTransaction( tags, tid );

	/* some of these may be NULL, that is OK */
	tagm_freeTag(t);
	tagm_freeTag(parent);
	tagm_freeTag(prev_sib);
	tagm_freeTag(next_sib);
	
	return result;
}


/* ************************************************************************
************************************************************************ */
TagStruct *tagm_readTag( TagManagerStruct *tags, off_t tag_loc, int bReadFullEntry )
{
	TagStruct *tag;
	tag = (TagStruct *)malloc( sizeof(TagStruct) );
#ifdef TRACE_TAGM_READTAG_MEM
	printf("readTag tag: 0x%x\n", tag );
#endif	
	memset( tag, 0, sizeof(TagStruct) );
	
	if( tagmt_pread(tags,&tag->hdr, sizeof(TagHdrStruct), tag_loc ) != sizeof(TagHdrStruct) )
	{
		printf("couldn't readTag (%s) at %ld\n", strerror(errno), (long int)tag_loc );
		free(tag);
		return NULL;
	}

	if( tag->hdr.klen > 0 && bReadFullEntry )
	{
		tag->key = (unsigned char *)malloc( tag->hdr.klen );
#ifdef TRACE_TAGM_READTAG_MEM		
		printf("readTag key: 0x%x\n", tag->key );
#endif		
		if( tagmt_pread(tags, tag->key, tag->hdr.klen, tag_loc+sizeof(TagHdrStruct) ) != tag->hdr.klen )
		{
			printf("couldn't readTag key (%s)\n", strerror(errno) );
			free(tag->key);
			tag->key = NULL;
		}

	}
	
	if( tag->hdr.dlen > 0 && bReadFullEntry )
	{
		tag->data = (unsigned char *)malloc( tag->hdr.dlen );
#ifdef TRACE_TAGM_READTAG_MEM				
		printf("readTag data: 0x%x\n", tag->data );		
#endif		
		if( tagmt_pread(tags, tag->data, tag->hdr.dlen, tag_loc+tag->hdr.klen+sizeof(TagHdrStruct) ) != tag->hdr.dlen )
		{
			printf("couldn't readTag data (%s)\n", strerror(errno) );
			free(tag->key);
			tag->key = NULL;
			free(tag->data);
			tag->data = NULL;
		}

	}
	
	return tag;
}



/* ************************************************************************
************************************************************************ */

/*!
	@function tagm_freeTag
	@abstract frees tag structure memory
	@discussion This function should be called on structure pointers
		received from tagm_* functions which return these types of
		pointers.
	@param tag The tag structure pointer to free; maybe NULL.
*/
void tagm_freeTag( TagStruct *tag )
{
	if(!tag)
		return;
	if( tag->data )
		free( tag->data );
	if( tag->key )
		free( tag->key );
	free( tag );
}


/* ************************************************************************
************************************************************************ */
/*!
	@function tagm_changeTagParent
	@abstract Appends an unlinked-tag into a new parent's linked-list
	@discussion Appends an unlinked-tag into a new parent's linked-list
		The item must have been previously unlinked before calling this
		function. If the item has not been unlinked the the original
		parent's linked-list will be corrupted.
	@param tags Tag manager context
	@param tag_loc the location of the tag to change
	@param new_parent_loc the location of the new parent's tag
	@result 0 on success; -1 on failure
*/
int tagm_changeTagParent( TagManagerStruct *tags, off_t tag_loc, off_t new_parent_loc )
{
	assert( tag_loc != 0ULL );				/* Can't change the root items parent! */
	assert( tag_loc != new_parent_loc );	/* Circular links would be bad */
	
	TagStruct *target = tagm_readTag( tags,	tag_loc, 0 );
	TagStruct *new_parent = NULL;
	TagStruct *last_tag = NULL;
	int result = -1;	/* assume error */
	int tid = -1;		/* assume error */
	
	if(!target)
		goto cleanup;
	
	new_parent = tagm_readTag( tags, new_parent_loc, 0 );
	if(!new_parent)
		goto cleanup;
	
	
	tid = tagmt_beginTransaction( tags );
	if(tid < 0)
		goto cleanup;

	target->hdr.parent = new_parent_loc;
	
	off_t new_parent_last_loc = new_parent->hdr.last;
	if( new_parent_last_loc == 0ULL )
	{
		assert( new_parent->hdr.first == 0ULL );	/* This would be a consistency error */
		new_parent->hdr.first = tag_loc;
		
		target->hdr.prev = 0ULL;
		target->hdr.next = 0ULL;
	}
	else
	{
		/* update the existing last item in the linked-list */
		last_tag = tagm_readTag( tags, new_parent_last_loc, 0 );
		if(!last_tag)
			goto cleanup;
		
		assert( last_tag->hdr.next == 0ULL );		/* This would be a consistency error */
		
		last_tag->hdr.next = tag_loc;
				
	
		if( tagmt_pwrite(tags,&last_tag->hdr,sizeof(TagHdrStruct), new_parent_last_loc ) != sizeof(TagHdrStruct) )
		{
			TAGM_ERROR(("couldn't %s (%s)\n", __FUNCTION__, strerror(errno) ));
			goto cleanup;
		}

		/* target should be linked */
		target->hdr.prev = new_parent_last_loc;
		target->hdr.next = 0ULL;		
	}

	/* append the new tag to the new parent */
	new_parent->hdr.last = tag_loc;


	/* write target tag header */
	if( tagmt_pwrite(tags,&target->hdr,sizeof(TagHdrStruct), tag_loc ) != sizeof(TagHdrStruct) )
	{
		TAGM_ERROR(("couldn't %s (%s)\n", __FUNCTION__, strerror(errno) ));
		goto cleanup;
	}	
	
	/* write new target's parent tag header */
	if( tagmt_pwrite(tags,&new_parent->hdr,sizeof(TagHdrStruct), new_parent_loc ) != sizeof(TagHdrStruct) )
	{
		TAGM_ERROR(("couldn't %s (%s)\n", __FUNCTION__, strerror(errno) ));
		goto cleanup;
	}	
		
	result = tagmt_endTransaction( tags, tid );
		
cleanup:
	/* Abort any mid-transaction failures: */
	if( result < 0 && tid > 0 )
		tagmt_abortTransaction( tags, tid );

	/* some of these may be NULL, that is OK */
	tagm_freeTag(target);
	tagm_freeTag(new_parent);
	tagm_freeTag(last_tag);
	
	return result;
}


/* ************************************************************************
************************************************************************ */
/*!
	@function tagm_replaceTag
	@abstract Replaces a tag with another tag
	@discussion The tag to be replaced will be unlinked, the children will
		be adopted by the new replacement tag. The replacement tag will be
		assigned to the original tags parent.
	@param tags Tag manager context
	@param tag_loc the location of the tag to replace
	@param replacement_tag_loc the location of the new tag
	@result 0 on success; -1 on failure
*/
int tagm_replaceTag( TagManagerStruct *tags, off_t tag_loc, off_t replacement_tag_loc )
{
	/* Currently a no-op:
		This function would need to visit and change the headers of all the children tags
		of the tag to be replaced
	*/
	return -1;
}


/* ************************************************************************
************************************************************************ */
/*!
	@function tagm_dumpTag
	@abstract Dumps the linked-list tree in a readable format
	@discussion tagm_dumpTag recursively describes the linked-list tree
		structure. Note: the function is recursively called with begin
		enum which mallocs a buffer, deep trees will cause lots of
		allocations.
	@param tags Tag manager context
	@param out_fp The 
	@param start_loc the starting location from which to start dumping
	@param indent indentation level, set to zero
*/
void tagm_dumpTag( TagManagerStruct *tags, FILE *out_fp, off_t start_loc, int indent )
{
	int i;
	TagStruct *tag;
	
	off_t tag_loc;
	
	TagManagerEnumStruct tmes;
	(void)i;
	
	if( tagm_beginEnumTags( tags, &tmes, start_loc ) )
		return;

	while( (tag = tagm_nextTag(tags, &tmes, &tag_loc)) )
	{
#ifdef TAGM_DUMP_DEBUG_TEXT	
		for( i = 0; i < indent; i ++ )
			fprintf(out_fp,"\t");
		
		fprintf(out_fp,"tag (next: %d, prev: %d, first: %d, last: %d, dlen: %d) key: \"", (int)tag->hdr.next, (int)tag->hdr.prev, (int)tag->hdr.first, (int)tag->hdr.last, (int)tag->hdr.dlen );
		fwrite( tag->key, tag->hdr.klen, 1, out_fp );
		fprintf(out_fp,"\"; data: \"");
		fwrite( tag->data, tag->hdr.dlen, 1, out_fp );
		fprintf(out_fp,"\";\n");
#elif TAGM_DUMP_DOT_FORMAT
		/* dot format */
		if( tag->hdr.first == 0ULL && tag->hdr.last == 0ULL )
			continue;	/* skip tags w/o children */
		fprintf(out_fp,"\ttag_loc_%d [label = \"", (int)tag_loc );
		for( i = 0; i < tag->hdr.klen; i ++ )
			fprintf(out_fp, "%c", (isalnum(tag->key[i])?tag->key[i]: '.') );
		fprintf(out_fp,"\"];\n" );
		fprintf(out_fp,"\t\ttag_loc_%d -> tag_loc_%d;\n", (int)start_loc, (int)tag_loc );
#else
		/* no format specified */
		
#endif
		tagm_dumpTag( tags, out_fp, tag_loc, indent + 1 );
	}
	
	tagm_endEnumTags( tags, &tmes );
}

/* ************************************************************************
************************************************************************ */
/*!
	@function tagm_duplicateTagFile
	@abstract Duplicates a tag file into another tag file
	@discussion 
	@param tags Tag manager context

*/
int tagm_duplicateTagFile( TagManagerStruct *source_tags, TagManagerStruct *dest_tags, off_t src_start_loc, off_t dst_start_loc )
{
	TagStruct *tag;
	off_t tag_loc;
	TagManagerEnumStruct tmes;
	int result = 0;
	if( tagm_beginEnumTags( source_tags, &tmes, src_start_loc ) )
		return -1;

	while( (tag = tagm_nextTag(source_tags, &tmes, &tag_loc)) )
	{	
		off_t new_tag_loc;
/*		fprintf(stderr,"tag loc: %d (next: %d, prev: %d, first: %d, last: %d, dlen: %d)\n", (int)tag_loc, (int)tag->hdr.next, (int)tag->hdr.prev, (int)tag->hdr.first, (int)tag->hdr.last, (int)tag->hdr.dlen ); */
		if( tag->hdr.bFlags & TAG_DELETED )
			continue;

		if( tagm_insertTag(dest_tags, dst_start_loc, tag, &new_tag_loc) )
		{
			fprintf(stderr,"tagm_insertTag failed\n");
			result = -1;
			break;
		}
		
		if( tagm_duplicateTagFile( source_tags, dest_tags, tag_loc, new_tag_loc ) )
		{
			fprintf(stderr,"tagm_insertTag failed\n");
			result = -1;
			break;
		}
	}
	
	tagm_endEnumTags( source_tags, &tmes );

	return result;
}

//#define REGRESSION_TEST
#ifdef REGRESSION_TEST
#include <time.h>




void exit_error( char *reason )
{
	printf("Error: %s\n", reason );
	exit(-1);
}

int insertItem( TagManagerStruct *tags, off_t root_loc, off_t *tag_loc, unsigned char *data, size_t data_sz )
{
	TagStruct new_tag;
	
	memset( &new_tag, 0, sizeof(TagStruct) );
	
	new_tag.hdr.bFlags = 0x00;
	new_tag.hdr.dlen = data_sz;
	new_tag.data = data;
	
	return tagm_insertTag( tags, root_loc, &new_tag, tag_loc );
}

int insertKeyedItem( TagManagerStruct *tags, off_t root_loc, off_t *tag_loc,  unsigned char *key, size_t key_sz, unsigned char *data, size_t data_sz )
{
	TagStruct new_tag;
	
	memset( &new_tag, 0, sizeof(TagStruct) );
	
	new_tag.hdr.bFlags = 0x00;
	new_tag.hdr.dlen = data_sz;
	new_tag.data = data;
	new_tag.hdr.klen = key_sz;
	new_tag.key = key;
	
	return tagm_insertTag( tags, root_loc, &new_tag, tag_loc );
}

#define dumpAllTags( tags, start_loc ) tagm_dumpTag( tags, stdout, start_loc, 0 );


void test_changeparent( TagManagerStruct *tags )
{
	//int tagm_changeTagParent( TagManagerStruct *tags, off_t tag_loc, off_t new_parent_loc )
	off_t tag_loc;
	off_t tag2_loc, tag3_loc;
	off_t parents_loc[3];
	off_t sub_tag_loc;
	char buf[256];
	char key_buf[256];
	int i, x;
	
	// zero file:
	tagm_zerofile( tags );
	
	sprintf( buf, "one" );
	assert( ! insertItem( tags, 0ULL, &parents_loc[0], (unsigned char *)buf, strlen(buf) ) );

	sprintf( buf, "two" );
	assert( ! insertItem( tags, 0ULL, &parents_loc[1], (unsigned char *)buf, strlen(buf) ) );

	sprintf( buf, "three" );
	assert( ! insertItem( tags, 0ULL, &parents_loc[2], (unsigned char *)buf, strlen(buf) ) );

	/* insert "one sub-item" into parent that has data: "one" */
	sprintf( buf, "one sub-item" );
	assert( ! insertItem( tags, parents_loc[0], &tag_loc, (unsigned char *)buf, strlen(buf) ) );

	/* insert "three sub-item" into parent that has data: "three" */
	sprintf( buf, "three sub-item" );
	assert( ! insertItem( tags, parents_loc[2], &tag2_loc, (unsigned char *)buf, strlen(buf) ) );

	printf("\nunlink and change parent\n");
	/* remove the item from that parent */
	assert( ! tagm_unlinkTag(tags, tag_loc) );
	/* assign it to a new parent that has data: "two" */
	assert( ! tagm_changeTagParent(tags, tag_loc, parents_loc[1] ) );
	
	dumpAllTags( tags, 0ULL );	

	printf("\nunlink and change parent 2\n");
	/* remove the item from that parent */
	assert( ! tagm_unlinkTag(tags, tag2_loc) );
	/* assign it to a new parent that has data: "two" */
	assert( ! tagm_changeTagParent(tags, tag2_loc, parents_loc[1] ) );
	
	dumpAllTags( tags, 0ULL );	
		
	printf("\nunlink and change parent 3\n");

	assert( ! tagm_unlinkTag(tags, parents_loc[1]) );
	assert( ! tagm_changeTagParent(tags, parents_loc[1], parents_loc[2] ) );
	
	dumpAllTags( tags, 0ULL );	

	printf("\nunlink and change parent 4\n");

	assert( ! tagm_unlinkTag(tags, parents_loc[2]) );
	assert( ! tagm_changeTagParent(tags, parents_loc[2], parents_loc[0] ) );
	
	dumpAllTags( tags, 0ULL );	

	printf("\nappend another item to \"three\"\n");
	sprintf( buf, "three sub-item #2" );
	assert( ! insertItem( tags, parents_loc[2], &tag3_loc, (unsigned char *)buf, strlen(buf) ) );
	dumpAllTags( tags, 0ULL );	

	printf("\nremove item \"one\"\n");
	assert( ! tagm_unlinkTag(tags, parents_loc[0]) );
	dumpAllTags( tags, 0ULL );	
	
	
}

void test_unlink( TagManagerStruct *tags )
{
	/*
	The test cases for unlinking:
	1. remove the only item in the parent's linked-list
	2. remove the first item in the parent's linked-list
	3. remove the last item in the parent's linked-list
	4. remove an item from the middle of a parent's linked-list
	*/
	off_t tag_loc;
	off_t tag2_loc, tag3_loc;
	off_t sub_tag_loc;
	char buf[256];
	char key_buf[256];
	int i, x;
		

	/* 1 */
	sprintf( buf, "only item" );
	assert( ! insertItem( tags, 0ULL, &tag_loc, (unsigned char *)buf, strlen(buf) ) );
	assert( ! tagm_unlinkTag(tags, tag_loc) );
	
	dumpAllTags( tags, 0ULL );


	/* 2 */
	sprintf( buf, "one" );
	assert( ! insertItem( tags, 0ULL, &tag_loc, (unsigned char *)buf, strlen(buf) ) );

	sprintf( buf, "two" );
	assert( ! insertItem( tags, 0ULL, &tag2_loc, (unsigned char *)buf, strlen(buf) ) );

	assert( ! tagm_unlinkTag(tags, tag_loc));
	assert( ! tagm_unlinkTag(tags, tag2_loc));

	
	dumpAllTags( tags, 0ULL );

	/* 3 */
	sprintf( buf, "one" );
	assert( ! insertItem( tags, 0ULL, &tag_loc, (unsigned char *)buf, strlen(buf) ) );

	sprintf( buf, "two" );
	assert( ! insertItem( tags, 0ULL, &tag2_loc, (unsigned char *)buf, strlen(buf) ) );


	assert( ! tagm_unlinkTag(tags, tag2_loc));
	assert( ! tagm_unlinkTag(tags, tag_loc));

	
	dumpAllTags( tags, 0ULL );

	/* 4 */
	sprintf( buf, "one" );
	assert( ! insertItem( tags, 0ULL, &tag_loc, (unsigned char *)buf, strlen(buf) ) );

	sprintf( buf, "two" );
	assert( ! insertItem( tags, 0ULL, &tag2_loc, (unsigned char *)buf, strlen(buf) ) );

	sprintf( buf, "three" );
	assert( ! insertItem( tags, 0ULL, &tag3_loc, (unsigned char *)buf, strlen(buf) ) );

	// remove middle:
	assert( ! tagm_unlinkTag(tags, tag2_loc));
	
	assert( ! tagm_unlinkTag(tags, tag_loc));
	assert( ! tagm_unlinkTag(tags, tag3_loc));

	
	dumpAllTags( tags, 0ULL );
//	sprintf( buf, "first subitem" );
//	if( insertItem( tags, tag_loc, &tag_loc, (unsigned char *)buf, strlen(buf) ) )
//		exit_error( "failed to do insertItem" );
		
}

int main( int argc, char *argv[] )
{
	TagManagerStruct *tags;
	off_t tag_loc;
	off_t sub_tag_loc;
	char buf[256];
	char key_buf[256];
	int i, x;
	
	printf("RTEST STARTS\n");
	printf("-------------------------------------------------------\n");
	
	if( !(tags = tagm_open("test_tags.tags")) )
		exit_error( "failed to do tagm_open" );

	
//	dumpAllTags( tags, 0ULL );

	

//	int tagm_insertTag( TagManagerStruct *tags, off_t root_loc, TagStruct *new_tag, off_t *new_tag_loc )
//	void insertItem( TagManagerStruct *tags, off_t root_loc, off_t *tag_loc, unsigned char *data, size_t data_sz )

	sprintf( buf, "first item" );
	if( insertItem( tags, 0ULL, &tag_loc, (unsigned char *)buf, strlen(buf) ) )
		exit_error( "failed to do insertItem" );

	sprintf( buf, "first subitem" );
	if( insertItem( tags, tag_loc, &tag_loc, (unsigned char *)buf, strlen(buf) ) )
		exit_error( "failed to do insertItem" );

	#define TEST_BRANCH_COUNT	10
	off_t tag_loc_array[TEST_BRANCH_COUNT];
	for( i = 0; i < TEST_BRANCH_COUNT; i ++ )
	{
		sprintf( buf, "root item: %d", i );
		if( insertItem( tags, 0ULL, &tag_loc_array[i], (unsigned char *)buf, strlen(buf) ) )
			exit_error( "failed to do insertItem" );
		
		for( x = 0; x < 200; x ++ )
		{
			sprintf( buf, "sub item %d:%d", i, x );
			if( insertItem( tags, tag_loc_array[i], &sub_tag_loc, (unsigned char *)buf, strlen(buf) ) )
				exit_error( "failed to do insertItem" );
		}
	}
	for( i = 0; i < TEST_BRANCH_COUNT; i ++ )
		assert( !tagm_unlinkTag(tags, tag_loc_array[i]) );
	

	sprintf( buf, "third item" );
	if( insertItem( tags, 0ULL, &tag_loc, (unsigned char *)buf, strlen(buf) ) )
		exit_error( "failed to do insertItem" );
	sprintf( buf, "second item->second subitem" );
	if( insertItem( tags, tag_loc, &sub_tag_loc, (unsigned char *)buf, strlen(buf) ) )
		exit_error( "failed to do insertItem" );

	sprintf( buf, "keyed item data 1" );
	sprintf( key_buf, "keyed item key #1" );
	if( insertKeyedItem( tags, 0ULL, &tag_loc, (unsigned char *)key_buf, strlen(key_buf), (unsigned char *)buf, strlen(buf) ) )
		exit_error( "failed to do insertItem" );

	sprintf( buf, "keyed item data 2" );
	sprintf( key_buf, "keyed item key #2" );
	if( insertKeyedItem( tags, 0ULL, &tag_loc, (unsigned char *)key_buf, strlen(key_buf), (unsigned char *)buf, strlen(buf) ) )
		exit_error( "failed to do insertItem" );

	sprintf( buf, "keyed item data 3" );
	sprintf( key_buf, "keyed sub-item key #1" );
	if( insertKeyedItem( tags, tag_loc, &sub_tag_loc, (unsigned char *)key_buf, strlen(key_buf), (unsigned char *)buf, strlen(buf) ) )
		exit_error( "failed to do insertItem" );


	dumpAllTags( tags, 0ULL );


	test_unlink(tags);

	test_changeparent( tags );

	
	tagm_close(tags);
	printf("-------------------------------------------------------\n");	
	printf("RTEST ENDS SUCCESSFULLY\n");
	return 0;
}


#endif






